public class Practice6 {
    //https://www.nowcoder.com/practice/2820ea076d144b30806e72de5e5d4bbf?tpId=196&tqId=37561&ru=/exam/oj
    //01背包问题, 可以参考我的博客https://blog.csdn.net/weixin_72779762/article/details/142027451?spm=1001.2014.3001.5501
    public int knapsack (int V, int n, int[][] vw) {
        // write code here
        int[][] dp = new int[n + 1][V + 1];
        for(int i = 1;i <= n;i++){
            for(int j = 1;j <= V;j++){
                dp[i][j] = dp[i - 1][j];
                if(j - vw[i - 1][0] >= 0){
                    dp[i][j] = Math.max(dp[i][j],dp[i - 1][j - vw[i - 1][0]] + vw[i - 1][1]);

                }
            }
        }
        System.out.println(dp[n][V]);
        return dp[n][V];
    }
    public static void main(String[] args) {

    }
}
